#include<iostream>
using namespace std;
void DownAdjust(int *a,int i,int len)
{
    int child=i*2+1;
    int parents=i;
    while(child<len)
    {
        if(child+1<len&&a[child]<a[child+1])
        {
            child++;
        }
        if(a[parents]<a[child])
            swap(a[parents], a[child]);
        parents=child;
        child=parents*2+1;
    }
}
void DeleteTop(int *a,int len)
{
    swap(a[0],a[len]);
    DownAdjust(a,0,len-1);
}
void HeapSort(int *a,int len)
{
    for(int i=len/2;i>=0;i--)
    {
        DownAdjust(a,i,len);
    }
    for(int i=0;i<len;i++)
    {
        DeleteTop(a,len-i-1);
    }
}
int main()
{
    int a[]={1,5,10,7,41,2,3,6};
    HeapSort(a,sizeof(a)/sizeof(a[0]));
    for(int i=0;i<8;i++)
        cout<<a[i]<<" ";
}